package Sort;

import java.util.Arrays;



/**
 * @author Liangyaoyun
 */
public class QuickSortPlus {
    public void dualPivotQuickSort(int[] nums) {
        dualPivotQuickSortInner(nums, 0, nums.length - 1);
    }

    private void dualPivotQuickSortInner(int[] nums, int start, int end) {

        if (end - start <= 0) {
            return;
        }

        int tmp;

        if (nums[start] > nums[end]) {
            tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
        }

        int pivot1 = nums[start];
        int pivot2 = nums[end];

        int lt = start + 1;
        int gt = end - 1;
        int i = start + 1;

        while (i <= gt) {
            if (nums[i] < pivot1) {
                tmp = nums[i];
                nums[i] = nums[lt];
                nums[lt] = tmp;
                i++;
                lt++;
            } else if (nums[i] >= pivot1 && nums[i] <= pivot2) {
                i++;
            } else {
                tmp = nums[i];
                nums[i] = nums[gt];
                nums[gt] = tmp;
                gt--;
            }
        }

        tmp = nums[start];
        nums[start] = nums[lt - 1];
        nums[lt - 1] = tmp;

        tmp = nums[end];
        nums[end] = nums[gt + 1];
        nums[gt + 1] = tmp;

        dualPivotQuickSortInner(nums, start, lt - 2);
        dualPivotQuickSortInner(nums, lt, gt);
        dualPivotQuickSortInner(nums, gt + 2, end);


    }
    public static void main(String[] args) {
        int[] nums = new int[]{9, 7, 4, 3, 2, 8, 5, 1, 6, 0};
        int[] nums1 = new int[]{8, 7, 4, 3, 2, 9, 5, 1, 6, 0};
        QuickSortPlus qs=new QuickSortPlus();
        qs.dualPivotQuickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}
